package org.chnxi.study.algorithm.dac;

/**
 * 分治算法-汉诺塔
 */
public class Hanoitower {

    public static void main(String[] args) {
        System.out.println("1层汉诺塔：");
        int count= hanoitower(1 );
        System.out.println("1层汉诺塔移动需要"+count+"步");
        System.out.println("==============================");
        System.out.println("2层汉诺塔：");
        count = hanoitower(2 );
        System.out.println("2层汉诺塔移动需要"+count+"步");
        System.out.println("==============================");
        System.out.println("5层汉诺塔：");
        count = hanoitower(5 );
        System.out.println("5层汉诺塔移动需要"+count+"步");
    }

    /**
     * 重载hanoitower方法
     * @param num
     * @return
     */
    public static int hanoitower(int num){
        int count = 0;
        return hanoitower(num , 'A' , 'B' , 'C' , count);
    }

    /**
     * 汉诺塔移动
     * @param num 汉诺塔层数
     * @param a 需要移动汉诺塔的位置
     * @param b 中间临时存放位置
     * @param c 移动至目标汉诺塔的位置
     * @param count 总步数
     * @return 汉诺塔移动的总步数
     */
    public static int hanoitower(int num , char a , char b , char c,int count){
        count++;
        if(num == 1){ //如果只有一个盘
            System.out.println("第一个盘从"+a+"->"+c);
        }else{ //如果有>=2个盘
            count = hanoitower(num - 1 , a , c ,b,count);
            System.out.println("第"+num+"个盘从"+a+"->"+c);
            count = hanoitower(num -1 , b , a , c,count);
        }
        return count;
    }

}
